'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-01 10:27:37
'''
#
# @lc app=leetcode.cn id=140 lang=python3
#
# [140] 单词拆分 II
#

# @lc code=start
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        if not wordDict:
            return 0
        dp = [0]*(len(s)+1)
        wordDict = set(wordDict)
        maxx = max([len(i) for i in wordDict])
        for i in range(len(s)):
            tmp = min(i, maxx)
            for j in range(tmp+1):
                if s[i-j:i+1] in wordDict:
                    if i-j==0:
                        dp[i+1]=1
                    else:
                        dp[i+1] += dp[i-j] if dp[i-j] else 0
        return dp[-1]

# @lc code=end

